package day_6_28;

public class Main2 {
    /**
     * 60. 排列序列
     * https://leetcode.cn/problems/permutation-sequence/description/
     */
    int nn,kk;
    int[] factorial;
    boolean[] visit = new boolean[10];
    StringBuffer ret = new StringBuffer();

    public String getPermutation(int n, int k) {
        nn = n;
        kk = k;
        calculateFactorial(); // 用来计算对应位置存在多少个排列序列

        dfs(0);

        return ret.toString();
    }

    public void calculateFactorial() {
        factorial = new int[nn + 1];
        factorial[0] = 1;
        for(int i = 1;i <= nn;i++) {
            factorial[i] = factorial[i - 1] * i;
        }
    }

    public void dfs(int pos) {
        if(pos == nn) {
            return;
        }

        // 计算还未确定的数字的全排列的个数
        // 比如，已经放入1了，之后剩余2,3,4 这三个数字，之后这3个数字的全排列为6，那么这个count = 6
        int  count = factorial[nn - 1 - pos];
        for(int i = 1;i <= nn;i++) {
            if(visit[i]) {
                continue;
            }
            if(count < kk) {
                // 要求的大于当前的 count ，说明这里没有需要的值，之后将次数进行减少，并且进行剪枝操作
                kk -= count;
                continue;
            }
            ret.append(i);
            visit[i] = true;
            dfs(pos + 1);
            // 找到直接进行返回
            return;
        }
    }
}
